/**
 * 
 */
package logic.algorithm;

import java.util.Iterator;
import java.util.PriorityQueue;
import java.util.Vector;

import datamodel.Grid;
import datamodel.GridElement;
import datamodel.GridElementState;

/**
 * @author Toa, Michelle, Steffen
 * @version final
 *
 */
public class Dijkstra implements Algorithm {

	boolean solved = false;
	Grid grid = null;
	GridElement start = null;
	
	//sorted container
	PriorityQueue<GridElement> queue = null;
	
	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#init(datamodel.Grid)
	 */
	@Override
	public void init(Grid grid) {
		//init grid
		this.grid = grid;
		
		//create queue
		queue = new PriorityQueue<GridElement>(11,new ComparatorDistance());
		
		//add neighbors of start node to the queue
		for(int y = 0; y < this.grid.getRows(); y++){
			for(int x = 0; x < this.grid.getColumns(); x++){
				if(grid.getElementAt(x, y).getState() != GridElementState.BLOCKED){
					grid.getElementAt(x, y).setDistance(Integer.MAX_VALUE);
					queue.add(grid.getElementAt(x, y));
				}
			}
		}
		
		start = grid.getStartElement();
		queue.remove(start);
		start.setDistance(0);
		queue.offer(start);
	}

	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#doNextStep()
	 */
	@Override
	public boolean doNextStep() {
			
		if(queue.isEmpty()){
			solved = true;
			return false;
		}
		
		/*if(queue.peek().getDistance() == -1){
			return true;
		}*/
		
		GridElement current = queue.remove();
		
		
		// get all diagonal neighbors of the current node
		Vector<GridElement> neighbors = grid.getNeighborsFrom(current, true).getNeighbors();
		// get all horizontal and vertical neighbors of the current node
		neighbors.addAll(grid.getNeighborsFrom(current, false).getNeighbors());
		
		Vector<Integer> wayCosts = grid.getNeighborsFrom(current, true).getWayCosts();
		wayCosts.addAll(grid.getNeighborsFrom(current, false).getWayCosts());
		
		Iterator<Integer> it = wayCosts.iterator();
		
		for(GridElement neighbor: neighbors){
			//neighbor.getState() == GridElementState.BLOCKED||
			if(neighbor.getState().getWayCost() == Integer.MAX_VALUE){
				queue.remove(neighbor);
				it.next();
				continue;
			}
			
			int cost = it.next();
			
			if(queue.contains(neighbor))
				updateDistance(current,neighbor,cost);
		}
		
		return true;
	}
	
	/**
	 * updates DistanceLabel of the given neighbor depending on the given current node and given cost
	 *
	 * @param current given current node
	 * @param neighbor given neighbor node
	 * @param cost given cost  
	 */
	private void updateDistance(GridElement current, GridElement neighbor,int cost){ 
		
		int distance = current.getDistance() + cost;
		
		if(distance < neighbor.getDistance()){
			queue.remove(neighbor);
			neighbor.setDistance(distance);
			neighbor.setPrecursor(current);
			queue.offer(neighbor);
		}
	}

	/* (non-Javadoc)
	 * @see logic.algorithm.Algorithm#isSolved()
	 */
	@Override
	public boolean isSolved() {
		return solved;
	}

}
